package com.nlp.trie.probSeg;

import java.util.ArrayList;
import java.util.Iterator;

public class Segmenter {

	TernarySearchTrie dict = TernarySearchTrie.getInstance();
	int[] prevNode;
	double[] prob;
	public ArrayList<Integer> split(String sentence){
		int sLen = sentence.length();//字符串长度
		AdjList g = new AdjList(sLen + 1);//存储所有被切分的可能的词
		int j;
		TernarySearchTrie.PrefixRet wordMatch = new TernarySearchTrie.PrefixRet();
		for(int i = 0; i < sLen;) {
			boolean match = dict.getMatch(sentence, i, wordMatch);
			if (match) {
				for (WordEntry word : wordMatch.values) {
					j = i+ word.word.length();
					double logProb = Math.log(word.freq) - Math.log(dict.n);
					g.addEdge(new CnToken(i, j, logProb, word.word));
				}
				i = wordMatch.end;
			}else {
				j = i +1;
				double logProb = Math.log(1) - Math.log(dict.n);
				g.addEdge(new CnToken(i, j, logProb, sentence.substring(i, j)));
				i = j;
			}
		}
		
		System.out.println(g.toString());
		//求解
		return maxProb(g);
	}

	/**
	 * 计算出最大概率的数组
	 * @param g
	 * @return
	 */
	private ArrayList<Integer> maxProb(AdjList g) {
		prevNode = new int[g.verticesNum];//最佳前驱节点
		prob = new double[g.verticesNum];//节点概率
		prob[0] = 0;//节点0的初始概率是1，取log后是0
		//按节点求最佳前驱
		for (int index = 1; index < g.verticesNum; index++) {
			getBestPrev(g, index);
		}
		
		ArrayList<Integer> ret = new ArrayList<>();
		//从右向左找最佳前驱节点
		for(int i = (g.verticesNum-1); i > 0; i = prevNode[i]) {
			ret.add(i);
		}
		return ret;
	}

	private void getBestPrev(AdjList g, int index) {
		Iterator<CnToken> it = g.getPrev(index);//得到前驱词集合
		double maxProb = Double.NEGATIVE_INFINITY;
		int maxNode = -1;
		while(it.hasNext()) {
			CnToken itr = it.next();
			double nodeProb = prob[itr.start] + itr.logProb;//候选节点概率
			if (nodeProb > maxProb) {//概率最大的算作最佳前驱
				maxNode = itr.start;
				maxProb = nodeProb;
			}
		}
		prob[index] = maxProb;//节点概率
		prevNode[index] = maxNode;//最佳前驱节点
	}
	
	public static void main(String[] args) {

		String sentence = "大学生活动中心";// "大学生活动中心";
		ArrayList<Integer> ret = (new Segmenter()).split(sentence);
		int preIndex = 0;
/*		for (Integer index : ret) {
			System.out.println(index);
			String value = sentence.substring(preIndex,index);
			System.out.println(value);
		}*/
		int start = 0;
		/*for (Integer end : ret) {
			System.out.print(sentence.substring(start, end) + "\n");
			start = end;
		}*/
		
		for (int i = (ret.size()-1); i >= 0; i--) {
			int end = ret.get(i);
			System.out.println(end);
			System.out.print(sentence.substring(start, end) + "\n");
			start = end;
		}
	}
	
}
